1. Field of the Invention
The present invention relates to a carry look ahead addition method and a device therefor and particularly relates to a carry look ahead addition method and a device therefor used in addition and subtraction by a digital computer.
2. Description of the Prior Art
Conventionally, addition and subtraction of two numbers are mainly processed by a carry look ahead type addition method. Suppose here that the two numbers to be added are A and B and their bit length is n (positive integer). The bit values for A are a(n-1), a(n-2), . . . , a1, a0 and the bit values for B are b(n-1), b(n-2), . . . , b1, b0.
The carry generation term g(n-1), g(n-2), . . . , g1 or g0 and the carry propagation term p(n-1), p(n-2), p1 or p0 are given by the following expressions (1) and (2): EQU pi=ai (+) bi (1) EQU gi=ai .cndot. bi (2)
where (+) indicates exclusive-OR. Next, the sum and the carry are supposed to be s(n-1), s(n-2), . . . , s1 or s0 and c(n-1), c(n-2), . . . , c1, c0 respectively. They can be represented by the expressions (3) and (4) below using gi and pi: EQU ci=pi+pi .cndot. c(i-1) (3) EQU si=pi (+) c(i-1) (4)
By determining the carries for all bits at a time using the expressions (3) and (4), the sum can be also determined at a time for all bits. An actual addition device usually comprises three sections: a generator for carry generation term and carry propagation term to execute the expressions (1) and (2) (a pg generator), a carry generator to execute the expression (3) and a sum generator to execute the expression (4).
Next, two conventional addition methods actually used will be described below. There are BLC (Binary Look-ahead Carry) addition method and BCLA (Block Carry Look Ahead) addition method.
Firstly, BLC method is described. By applying the expression (3) to the bits with supposing the carry input to be cin, the following expression (5) can be obtained: ##EQU1##
The concept of block carry generation term and block carry propagation term applies here. For addition of values having n bits, a block carry generation term indicates whether a carry is generated or not within a block when considering such n bits to be constituted by continuous blocks each having an arbitrary number of bits. A block carry propagation term indicates whether a carry input from a lower block causes propagation of carry to the upper block or not. Focusing now on the i-th bit (i&lt;n), suppose that the bits from the i-th bit to the least significant bit constitute a single block. Then, the block carry generation term (Gi) and the block carry propagation term (Pi) can be represented as follows. ##EQU2## Accordingly, the carry at each bit can be determined by the following expression (7). EQU ci=Gi+Pi .cndot. cin (7)
Here, an operator (.cndot.) is defined as follows. EQU (g0, p0) (.cndot.) (g1, p1)=(g0+(p0 .cndot. g1), p0 .cndot. p1) (8)
This operator (.cndot.) is of coupling type and, when this is applied to the expression (6), the following expression can be obtained:
if i=1:
(Gi, Pi)=(g1, p1)
if 2&lt;i: ##EQU3##
In the BLC addition, logic gates for this operator are disposed in a binary tree representation so that the block carry generation term (Gi) and the block carry propagation term (Pi) for each bit expressed by the expression (6) are determined at a time.
FIG. 3 is a block diagram to illustrate the configuration of an 8-bit carry look ahead addition device based on the conventional BLC addition method. As shown in the figure, a conventional device for BLC addition method comprises a pg generator 60 which executes the expressions (1) and (2) to generate the carry generation term and the carry propagation term, a sum generator 61 which executes the expression (4), and a carry generator 62 which executes the expression (3).
The carry generator 62 further comprises a carry processor 65 consisting of eight carry generating cells 67, BLC cells 66 as logic gates to execute the operator (.cndot.) and buffer cells 68.
The BLC cell 66 has, as shown in FIG. 4, two AND gates and an OR gate. The carry generation cell 67 is to execute the expression (7) and, as shown in FIG. 5, comprises an AND gate and an OR gate. The buffer cell 68 has two buffers.
Now, the flow of processing at the 8-bit carry look ahead addition device based on the BLC addition method is described. Firstly, the pg generator 60 generates the carry generation term gi and the carry propagation term pi for all bits and inputs them to the carry generator 62. The block carry generation term Gi and the block carry propagation term Pi are generated here with considering the bits from the current bit to the least significant bit to be a single block. These block carry generation term Gi and the block carry propagation term Pi are, together with the carry input cin, input to the carry processor 65 and the carry ci is generated. The carry ci is input to the sum generator 61 together with the carry propagation term pi generated by the pg generator 60 so that the sum is determined.
Next, BCLA addition method will be described below following its procedures. Firstly, two input numbers are divided into some blocks each having several bits (For example, a 32 bit number is usually divided into eight 4-bit blocks). For each block, the block carry generation term and the block carry propagation term are determined. Then, the output block carry generation term and the block carry propagation term above are again divided into some blocks each having several bits and then the block carry generation term and the block carry propagation term are determined for each of such blocks. The above processing is repeated until the number of bits in the output block carry generation term and the block carry propagation becomes about 2 to 4 only. Finally, based on the carry input as well as the finally output block carry generation term and the block carry propagation term, the carry for each bit is generated.
FIG. 6 shows a schematic circuit diagram of a conventional BCLA unit for 4-bit blocks which determines the block carry generation term and the block carry propagation term and generates a carry for each bit. In the figure, a BCLA unit 30 comprises a carry look ahead circuit (CLA) 31 for three bits and a block carry generation term (G) and the block carry propagation term (P) generation circuit (BPG) 32. The terms P and G are expressed as follows. EQU P=p3 .cndot. p2 .cndot. p1.cndot. p0 G=g3+p3 .cndot. g2+p2 .cndot. g1+p3 .cndot. p2 .cndot. p1 .cndot. p0 (10)
In other words, G indicates whether a carry is generated or not in a 4-bit block and P indicates whether or not a carry in a 4-bit block is propagated to the upper block. Such a circuit is usually called a BCLA (Block Carry Look Ahead) unit.
FIG. 7 is a block diagram to show an example of a 32-bit carry look ahead addition device based on the conventional BCLA addition method using BCLA units as shown in FIG. 6. For convenience of explanation, a BCLA unit in FIG. 6 is divided into a 4-bit BPG unit and a 3-bit CLA unit in FIG. 7.
As shown in FIG. 7, a conventional carry look ahead addition device using the conventional BCLA addition method comprises a 32-bit carry generation term and carry propagation term generator (pg generator) 80, a carry generator 82 and a sum generator 81. The carry generator 82 comprises 4-bit BPGs 201 to 208, 301 and 302 and 2-bit CLAs 401 and 402 and 3-bit CLAs 211 to 218, 311 and 312. The CLA 401 is provided with three AND gates and two OR gates as shown in FIG. 8.
Now, the flow of processing at the carry look ahead addition device based on the BCLA addition method is described. Firstly, the pg generator 80 generates the carry propagation term pi and the carry generation term gi for all bits and inputs them to the carry generator 82. The input carry generation terms and the carry propagation terms for the bits are divided into eight 4-bit blocks. These blocks are input to eight 4-bit BPGs 201 to 208 so that eight pairs of block carry generation term and block carry propagation term are generated. They are divided again into two 4-bit blocks and sent to the 4-bit BPGs 301 and 302 on the next stage, where two new pairs of block carry generation term and block carry propagation term are generated. These two pairs of block carry generation term and block carry propagation term are sent to the 2-bit CLA 401 on the next stage, where the carry output "cout" and the carry c15 from the 15th bit are generated.
Such carry c15 and the carry input cin are input to the 3-bit CLAs 311 and 312, and the carries c3, c7 and c11 (at the CLA 311) and the carries c19, c23 and c27 (at the CLA 312) are generated. Further, the carries cin, c3, c7, c11, c15, c19, c23 and c27 are input to the 3-bit CLAs 211 to 218 respectively, which causes generation of carries for the remaining bits. Such carries are input to the sum generator 81 together with the carry propagation term pi for each bit generated at the pg generator 80 so that the sum is generated.
In this embodiment, a carry look ahead addition device based on the BCLA addition method comprises eight pairs of 4-bit BCLA units each combining BPG 201 and CLA 211, BPG 202 and CLA 212, . . . , BPG 208 and CLA 218, two pairs of 4-bit BCLA units each combining BPG 301 and CLA 311 and BPG 302 and CLA 312, as well as a 2-bit CLA 401. However, it may also comprises eight 4-bit BCLA units and an 8-bit CLA. In either case, the basic concept is the same and this concept can be embodied in various configurations.
When using the above conventional carry look ahead addition methods and devices therefor, either of the methods and devices calculates the block carry generation term and the block carry propagation term so as to generate the carry for each bit from the carry input and the above terms. Supply of the carry input via a route separate from other input data increases the number of stages and logic gates in the carry propagation route, which results in increased delay time and larger power consumption.